package com.ls.tree;

class BSTIterator {

    TreeNode cur;

    public BSTIterator(TreeNode root) {
        cur = root;
    }
    
    public int next() {
        TreeNode mostRight = null;
        int val = 0;
        while(cur != null){

            if(cur.left != null){
                // 寻找最右节点，即前驱节点
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                if(mostRight.right == cur){
                    val = cur.val;
//                    System.out.print(cur + " "); // 中序遍历
                    mostRight.right = null;
                    cur = cur.right;
                    break;

                }else{
                    mostRight.right = cur;
                    cur = cur.left;
//                    System.out.print(cur + " "); // 后续遍历
                }

            }else{
                val = cur.val;
//                System.out.print(cur + " ");  // 中序遍历
                cur = cur.right;
//                System.out.print(cur + " ");  // 后续遍历
                break;
            }
        }

        return val;
    }
    
    public boolean hasNext() {
        return cur != null;
    }

}